package q450_deleteNode;

import CommonClass.Common.TreeNode;
public class Solution_1 {

    /*
    此题和701的递归解法几乎一致，701是添加节点
    而该题则是对于节点需要进行删除处理
    基本的想法是 根据二叉搜索树的特性
    如果找到了该值所在的节点
    那么就把该节点 *左侧的节点* 添加到其 *右侧的节点* 的 *左叶子节点* 上
     */
    public TreeNode deleteNode(TreeNode root, int key) {

        // 先判断空值
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            if (root.right != null) {
                TreeNode rightNode = root.right;
                while (rightNode.left != null) {
                    rightNode = rightNode.left;
                }
                rightNode.left = root.left;
                return root.right;
            }else {
                return root.left;
            }
        }
        // 如果root值大于val 则往左搜索找节点插入的位置
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        }
        // 小于则往右
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }

        return root;
    }
}
